SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Importance sampling</title>

</head>

Importance sampling

</h1>

</header>

Importance sampling is a <a href="Monte_Carlo_method" title="Monte Carlo method">Monte Carlo method</a> for evaluating properties of a particular <a href="Probability_distribution" title="Probability distribution">distribution</a>, while only having samples generated from a different distribution than the distribution of interest. Its introduction in statistics is generally attributed to a paper by <a href="Teun_Kloek" title="Teun Kloek">Teun Kloek</a> and <a href="Herman_K._van_Dijk" title="Herman K. van Dijk">Herman K. van Dijk</a> in 1978,<a href="#cite_note-1">[1]</a> but its precursors can be found in <a href="Monte_Carlo_method_in_statistical_physics" class="mw-redirect" title="Monte Carlo method in statistical physics">statistical physics</a> as early as 1949.<a href="#cite_note-2">[2]</a><a href="#cite_note-3">[3]</a> Importance sampling is also related to <a href="Umbrella_sampling" title="Umbrella sampling">umbrella sampling</a> in <a href="Computational_physics" title="Computational physics">computational physics</a>. Depending on the application, the term may refer to the process of sampling from this alternative distribution, the process of inference, or both.

<div class="mw-heading mw-heading2"><h2 id="Basic_theory">Basic theory</h2></div>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\colon \Omega \to \mathbb {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\colon \Omega \to \mathbb {R} }</annotation>

</semantics>

</math><img src="./b68ecb50490003c72b7d6627145965f602b302b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.984ex; height:2.176ex;" alt="{\displaystyle X\colon \Omega \to \mathbb {R} }" loading="lazy"> be a <a href="Random_variable" title="Random variable">random variable</a> in some <a href="Probability_space" title="Probability space">probability space</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\Omega ,{\mathcal {F}},\mathbb {P} )}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\Omega ,{\mathcal {F}},\mathbb {P} )}</annotation>

</semantics>

</math><img src="./6bb8743f7565082ed1a9ee0490d9d71be82eafaa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.902ex; height:2.843ex;" alt="{\displaystyle (\Omega ,{\mathcal {F}},\mathbb {P} )}" loading="lazy">. We wish to estimate the <a href="Expected_value" title="Expected value">expected value</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> under <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {P} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {P} }</annotation>

</semantics>

</math><img src="./1053af9e662ceaf56c4455f90e0f67273422eded.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.42ex; height:2.176ex;" alt="{\displaystyle \mathbb {P} }" loading="lazy">, denoted <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}</annotation>

</semantics>

</math><img src="./2585ab6ca0ec270b5cae3475d87e46453b68a1e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.061ex; height:2.843ex;" alt="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}" loading="lazy">. If we have statistically independent random samples <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{1},\ldots ,X_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{1},\ldots ,X_{n}}</annotation>

</semantics>

</math><img src="./ac794f5521dcce89913085a6d566e7cdb615dbb0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.299ex; height:2.509ex;" alt="{\displaystyle X_{1},\ldots ,X_{n}}" loading="lazy">, generated according to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {P} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {P} }</annotation>

</semantics>

</math><img src="./1053af9e662ceaf56c4455f90e0f67273422eded.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.42ex; height:2.176ex;" alt="{\displaystyle \mathbb {P} }" loading="lazy">, then an empirical estimate of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}</annotation>

</semantics>

</math><img src="./2585ab6ca0ec270b5cae3475d87e46453b68a1e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.061ex; height:2.843ex;" alt="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}" loading="lazy"> is just

<msub>

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\widehat {\mathbb {E} }}_{\mathbb {P} }[X]={\frac {1}{n}}\sum _{i=1}^{n}X_{i}\quad \mathrm {where} \;X_{i}\sim \mathbb {P} (X)}</annotation>

</semantics>

</math><img src="./b93e408df802e0c285f33ee6c6fecc5e02df0a36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:38.19ex; height:6.843ex;" alt="{\displaystyle {\widehat {\mathbb {E} }}_{\mathbb {P} }[X]={\frac {1}{n}}\sum _{i=1}^{n}X_{i}\quad \mathrm {where} \;X_{i}\sim \mathbb {P} (X)}" loading="lazy"></dd></dl>

and the precision of this estimate depends on the variance of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy">:

<msub>

</mrow>

</msub>

</mrow>

<msub>

<mover>

</mrow>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {var} _{\mathbb {P} }{\big [}{\widehat {\mathbb {E} }}_{\mathbb {P} }[X]{\big ]}={\frac {\operatorname {var} _{\mathbb {P} }[X]}{n}}.}</annotation>

</semantics>

</math><img src="./ff8c49d12425cc06705f6b2b8488119027a71746.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:25.318ex; height:5.676ex;" alt="{\displaystyle \operatorname {var} _{\mathbb {P} }{\big [}{\widehat {\mathbb {E} }}_{\mathbb {P} }[X]{\big ]}={\frac {\operatorname {var} _{\mathbb {P} }[X]}{n}}.}" loading="lazy"></dd></dl>

The basic idea of importance sampling is to sample from a different distribution to lower the variance of the estimation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}</annotation>

</semantics>

</math><img src="./2585ab6ca0ec270b5cae3475d87e46453b68a1e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.061ex; height:2.843ex;" alt="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}" loading="lazy">, or when sampling directly from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {P} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {P} }</annotation>

</semantics>

</math><img src="./1053af9e662ceaf56c4455f90e0f67273422eded.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.42ex; height:2.176ex;" alt="{\displaystyle \mathbb {P} }" loading="lazy"> is difficult.

This is accomplished by first choosing a random variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y\geq 0}</annotation>

</semantics>

</math><img src="./037f579feb954c0739637be30f746e0bf76e88b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.034ex; height:2.343ex;" alt="{\displaystyle Y\geq 0}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} _{\mathbb {P} }[Y]=1}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} _{\mathbb {P} }[Y]=1}</annotation>

</semantics>

</math><img src="./52c2eca916fa45628e1b62e5612773faf3b973e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.115ex; height:2.843ex;" alt="{\displaystyle \mathbb {E} _{\mathbb {P} }[Y]=1}" loading="lazy"> and that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {P} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {P} }</annotation>

</semantics>

</math><img src="./1053af9e662ceaf56c4455f90e0f67273422eded.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.42ex; height:2.176ex;" alt="{\displaystyle \mathbb {P} }" loading="lazy">-<a href="Almost_everywhere" title="Almost everywhere">almost everywhere</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y(\omega )\neq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y(\omega )\neq 0}</annotation>

</semantics>

</math><img src="./a230dc16529fb822f6597ead316fe3bdb09efaf6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.289ex; height:2.843ex;" alt="{\displaystyle Y(\omega )\neq 0}" loading="lazy">.

With the variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> we define a probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Q} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Q} }</annotation>

</semantics>

</math><img src="./c5909f0b54e4718fa24d5fd34d54189d24a66e9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.808ex; height:2.509ex;" alt="{\displaystyle \mathbb {Q} }" loading="lazy"> that satisfies

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} _{\mathbb {P} }[X]=\mathbb {E} _{\mathbb {Q} }\left[{\frac {X}{Y}}\right].}</annotation>

</semantics>

</math><img src="./912866a09a45f368468412bfafba9bc2f06437b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:18.912ex; height:6.176ex;" alt="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]=\mathbb {E} _{\mathbb {Q} }\left[{\frac {X}{Y}}\right].}" loading="lazy"></dd></dl>

The variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X/Y}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X/Y}</annotation>

</semantics>

</math><img src="./b5c21f71ffba4f60a9c805ffb509a370f1e9c547.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.916ex; height:2.843ex;" alt="{\displaystyle X/Y}" loading="lazy"> will thus be sampled under <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Q} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Q} }</annotation>

</semantics>

</math><img src="./c5909f0b54e4718fa24d5fd34d54189d24a66e9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.808ex; height:2.509ex;" alt="{\displaystyle \mathbb {Q} }" loading="lazy"> to estimate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}</annotation>

</semantics>

</math><img src="./2585ab6ca0ec270b5cae3475d87e46453b68a1e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.061ex; height:2.843ex;" alt="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}" loading="lazy"> as above and this estimation is improved when

<msub>

</mrow>

</msub>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {var} _{\mathbb {Q} }\left[{\frac {X}{Y}}\right]<\operatorname {var} _{\mathbb {P} }[X].}</annotation>

</semantics>

</math><img src="./e98e00c6ffe29e72e9c71fc245fdf82348d0ae11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:21.641ex; height:6.176ex;" alt="{\displaystyle \operatorname {var} _{\mathbb {Q} }\left[{\frac {X}{Y}}\right]<\operatorname {var} _{\mathbb {P} }[X].}" loading="lazy"></dd></dl>

When <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> is of constant sign over <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>

</semantics>

</math><img src="./24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy">, the best variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> would clearly be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y^{*}={\frac {X}{\mathbb {E} _{\mathbb {P} }[X]}}\geq 0}">

<msup>

</mrow>

</msup>

<mfrac>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y^{*}={\frac {X}{\mathbb {E} _{\mathbb {P} }[X]}}\geq 0}</annotation>

</semantics>

</math><img src="./a87a51beef3280e0435a3ecd4dfe0d46d459795d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:17.211ex; height:6.009ex;" alt="{\displaystyle Y^{*}={\frac {X}{\mathbb {E} _{\mathbb {P} }[X]}}\geq 0}" loading="lazy">, so that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X/Y^{*}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X/Y^{*}}</annotation>

</semantics>

</math><img src="./8b7d4188537614af3287f0f9c549dfe72254d2ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.097ex; height:2.843ex;" alt="{\displaystyle X/Y^{*}}" loading="lazy"> is the searched constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}</annotation>

</semantics>

</math><img src="./2585ab6ca0ec270b5cae3475d87e46453b68a1e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.061ex; height:2.843ex;" alt="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}" loading="lazy"> and a single sample under <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Q} ^{*}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Q} ^{*}}</annotation>

</semantics>

</math><img src="./ebbb0fb3cce7d656ef9794f945b6dd0f11496be4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.862ex; height:2.676ex;" alt="{\displaystyle \mathbb {Q} ^{*}}" loading="lazy"> suffices to give its value. Unfortunately we cannot take that choice, because <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}</annotation>

</semantics>

</math><img src="./2585ab6ca0ec270b5cae3475d87e46453b68a1e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.061ex; height:2.843ex;" alt="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}" loading="lazy"> is precisely the value we are looking for! However this theoretical best case <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y^{*}}</annotation>

</semantics>

</math><img src="./5df6b56e280c170dd2e9844b966dd0f1aeb12ea0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:2.954ex; height:2.176ex;" alt="{\displaystyle Y^{*}}" loading="lazy"> gives us an insight into what importance sampling does: for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \mathbb {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \mathbb {R} }</annotation>

</semantics>

</math><img src="./a9c6d458566aec47a7259762034790c8981aefab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.848ex; height:2.176ex;" alt="{\displaystyle x\in \mathbb {R} }" loading="lazy">, the density of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Q} ^{*}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Q} ^{*}}</annotation>

</semantics>

</math><img src="./ebbb0fb3cce7d656ef9794f945b6dd0f11496be4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.862ex; height:2.676ex;" alt="{\displaystyle \mathbb {Q} ^{*}}" loading="lazy"> at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X=x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X=x}</annotation>

</semantics>

</math><img src="./0661396d873679039ffe8e908a39f02402d4912d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.408ex; height:2.176ex;" alt="{\displaystyle X=x}" loading="lazy"> can be written as

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\mathbb {Q} ^{*}{\big (}X\in [x;x+dx]{\big )}&=\int _{\omega \in \{X\in [x;x+dx]\}}{\frac {X(\omega )}{\mathbb {E} _{\mathbb {P} }[X]}}\,d\mathbb {P} (\omega )\\[6pt]&={\frac {1}{\mathbb {E} _{\mathbb {P} }[X]}}\;x\,\mathbb {P} (X\in [x;x+dx]).\end{aligned}}}</annotation>

</semantics>

</math><img src="./4e78fb84cac790e437cb1639a8ece78efbfe28f2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.505ex; width:52.364ex; height:14.176ex;" alt="{\displaystyle {\begin{aligned}\mathbb {Q} ^{*}{\big (}X\in [x;x+dx]{\big )}&=\int _{\omega \in \{X\in [x;x+dx]\}}{\frac {X(\omega )}{\mathbb {E} _{\mathbb {P} }[X]}}\,d\mathbb {P} (\omega )\\[6pt]&={\frac {1}{\mathbb {E} _{\mathbb {P} }[X]}}\;x\,\mathbb {P} (X\in [x;x+dx]).\end{aligned}}}" loading="lazy"></dd></dl>

To the right, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\,\mathbb {P} (X\in [x;x+dx])}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\,\mathbb {P} (X\in [x;x+dx])}</annotation>

</semantics>

</math><img src="./5c8a16b36af9c884af258127294bec2535c88e55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.14ex; height:2.843ex;" alt="{\displaystyle x\,\mathbb {P} (X\in [x;x+dx])}" loading="lazy"> is one of the infinitesimal elements that sum up to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}</annotation>

</semantics>

</math><img src="./2585ab6ca0ec270b5cae3475d87e46453b68a1e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.061ex; height:2.843ex;" alt="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}" loading="lazy">:

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} _{\mathbb {P} }[X]=\int _{-\infty }^{+\infty }x\,\mathbb {P} (X\in [x;x+dx])}</annotation>

</semantics>

</math><img src="./850ba8c83d7c8212f047c92e9eec5f4e28c266ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:35.304ex; height:6.176ex;" alt="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]=\int _{-\infty }^{+\infty }x\,\mathbb {P} (X\in [x;x+dx])}" loading="lazy"></dd></dl>

therefore, a good probability change <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Q} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Q} }</annotation>

</semantics>

</math><img src="./c5909f0b54e4718fa24d5fd34d54189d24a66e9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.808ex; height:2.509ex;" alt="{\displaystyle \mathbb {Q} }" loading="lazy"> in importance sampling will redistribute the law of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> so that its samples' frequencies are sorted directly according to their contributions in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}</annotation>

</semantics>

</math><img src="./2585ab6ca0ec270b5cae3475d87e46453b68a1e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.061ex; height:2.843ex;" alt="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}" loading="lazy"> as opposed to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} _{\mathbb {P} }[1]}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} _{\mathbb {P} }[1]}</annotation>

</semantics>

</math><img src="./d2d5ccfe2c54fbec47030bf648d7862fd765c3e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.243ex; height:2.843ex;" alt="{\displaystyle \mathbb {E} _{\mathbb {P} }[1]}" loading="lazy">. Hence the name "importance sampling."

Importance sampling is often used as a <a href="Monte_Carlo_integration" title="Monte Carlo integration">Monte Carlo integrator</a>.

When <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {P} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {P} }</annotation>

</semantics>

</math><img src="./1053af9e662ceaf56c4455f90e0f67273422eded.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.42ex; height:2.176ex;" alt="{\displaystyle \mathbb {P} }" loading="lazy"> is the uniform distribution over <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega =\mathbb {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega =\mathbb {R} }</annotation>

</semantics>

</math><img src="./fa509a134d45e796a6c29cf98237b4a2ff85fd8e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.455ex; height:2.176ex;" alt="{\displaystyle \Omega =\mathbb {R} }" loading="lazy">, the expectation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}</annotation>

</semantics>

</math><img src="./2585ab6ca0ec270b5cae3475d87e46453b68a1e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.061ex; height:2.843ex;" alt="{\displaystyle \mathbb {E} _{\mathbb {P} }[X]}" loading="lazy"> corresponds to the integral of the real function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\colon \mathbb {R} \to \mathbb {R} }">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\colon \mathbb {R} \to \mathbb {R} }</annotation>

</semantics>

</math><img src="./843b834701cd225904df7352b22105e891957468.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.984ex; height:2.176ex;" alt="{\displaystyle X\colon \mathbb {R} \to \mathbb {R} }" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Application_to_probabilistic_inference">Application to probabilistic inference</h2></div>

Such methods are frequently used to estimate posterior densities or expectations in state and/or parameter estimation problems in probabilistic models that are too hard to treat analytically. Examples include <a href="Bayesian_network" title="Bayesian network">Bayesian networks</a> and importance weighted <a href="Variational_autoencoder" title="Variational autoencoder">variational autoencoders</a>.<a href="#cite_note-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Application_to_simulation">Application to simulation</h2></div>

Importance sampling is a <a href="Variance_reduction" title="Variance reduction">variance reduction</a> technique that can be used in the <a href="Monte_Carlo_method" title="Monte Carlo method">Monte Carlo method</a>. The idea behind importance sampling is that certain values of the input <a href="Random_variables" class="mw-redirect" title="Random variables">random variables</a> in a <a href="Simulation" title="Simulation">simulation</a> have more impact on the parameter being estimated than others. If these "<a href="Important" class="mw-redirect" title="Important">important</a>" values are emphasized by sampling more frequently, then the <a href="Estimator" title="Estimator">estimator</a> variance can be reduced. Hence, the basic methodology in importance sampling is to choose a distribution which "encourages" the important values. This use of "biased" distributions will result in a biased estimator if it is applied directly in the simulation. However, the simulation outputs are weighted to correct for the use of the biased distribution, and this ensures that the new importance sampling estimator is unbiased. The weight is given by the <a href="Likelihood-ratio_test" title="Likelihood-ratio test">likelihood ratio</a>, that is, the <a href="Radon%E2%80%93Nikodym_derivative" class="mw-redirect" title="Radon–Nikodym derivative">Radon–Nikodym derivative</a> of the true underlying distribution with respect to the biased simulation distribution.

The fundamental issue in implementing importance sampling simulation is the choice of the biased distribution which encourages the important regions of the input variables. Choosing or designing a good biased distribution is the "art" of importance sampling. The rewards for a good distribution can be huge run-time savings; the penalty for a bad distribution can be longer run times than for a general Monte Carlo simulation without importance sampling.

Consider <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> to be the sample and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {f(X)}{g(X)}}}">

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {f(X)}{g(X)}}}</annotation>

</semantics>

</math><img src="./d583862871298de33e0d68a8e1ce656198dc90fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:5.904ex; height:6.509ex;" alt="{\displaystyle {\frac {f(X)}{g(X)}}}" loading="lazy"> to be the likelihood ratio, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is the probability density (mass) function of the desired distribution and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> is the probability density (mass) function of the biased/proposal/sample distribution. Then the problem can be characterized by choosing the sample distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> that minimizes the variance of the scaled sample:

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g^{*}=\min _{g}\operatorname {var} _{g}\left(X{\frac {f(X)}{g(X)}}\right).}</annotation>

</semantics>

</math><img src="./e871e422b2c0a9841ea3927ab65dc9a5ced51d52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:25.808ex; height:6.509ex;" alt="{\displaystyle g^{*}=\min _{g}\operatorname {var} _{g}\left(X{\frac {f(X)}{g(X)}}\right).}" loading="lazy"></dd></dl>

It can be shown that the following distribution minimizes the above variance:<a href="#cite_note-5">[5]</a>

<msup>

</mrow>

</msup>

<mfrac>

<mrow>

</mrow>

</mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g^{*}(X)={\frac {|X|f(X)}{\int |x|f(x)\,dx}}.}</annotation>

</semantics>

</math><img src="./3f53ca046fca0cfe614e0f18a2c8bd9961b8a08b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:22.322ex; height:6.676ex;" alt="{\displaystyle g^{*}(X)={\frac {|X|f(X)}{\int |x|f(x)\,dx}}.}" loading="lazy"></dd></dl>

Notice that when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\geq 0}</annotation>

</semantics>

</math><img src="./de5066700163970af13a0196910d43f2b4d8e41b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.241ex; height:2.343ex;" alt="{\displaystyle X\geq 0}" loading="lazy">, this variance becomes 0.

<div class="mw-heading mw-heading3"><h3 id="Mathematical_approach">Mathematical approach</h3></div>

Consider estimating by simulation the probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{t}\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{t}\,}</annotation>

</semantics>

</math><img src="./0cb80d4b388c2ad1595cef75858a576030bac8a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.472ex; height:2.009ex;" alt="{\displaystyle p_{t}\,}" loading="lazy"> of an event <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\geq t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\geq t}</annotation>

</semantics>

</math><img src="./1f1ab3d9bc1ae8800861a0bf4ebe89043a154d8b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.918ex; height:2.343ex;" alt="{\displaystyle X\geq t}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> is a random variable with <a href="Cumulative_distribution_function" title="Cumulative distribution function">cumulative distribution function</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(x)}</annotation>

</semantics>

</math><img src="./71a82805d469cdfa7856c11d6ee756acd1dc7174.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.88ex; height:2.843ex;" alt="{\displaystyle F(x)}" loading="lazy"> and <a href="Probability_density_function" title="Probability density function">probability density function</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)=F'(x)\,}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=F'(x)\,}</annotation>

</semantics>

</math><img src="./28baf36b53b2237822430958d8574dbe2163e8cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.542ex; height:3.009ex;" alt="{\displaystyle f(x)=F'(x)\,}" loading="lazy">, where prime denotes <a href="Derivative" title="Derivative">derivative</a>. A <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy">-length <a href="Independent_and_identically_distributed" class="mw-redirect" title="Independent and identically distributed">independent and identically distributed</a> (i.i.d.) sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i}\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{i}\,}</annotation>

</semantics>

</math><img src="./575a2898399d67057fc9783606997825aa190d23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.111ex; height:2.509ex;" alt="{\displaystyle X_{i}\,}" loading="lazy"> is generated from the distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F}</annotation>

</semantics>

</math><img src="./545fd099af8541605f7ee55f08225526be88ce57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}" loading="lazy">, and the number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{t}}</annotation>

</semantics>

</math><img src="./352386366dcb1dcc184d82669513975561f2d2ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.037ex; height:2.509ex;" alt="{\displaystyle k_{t}}" loading="lazy"> of random variables that lie above the threshold <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> are counted. The random variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{t}}</annotation>

</semantics>

</math><img src="./352386366dcb1dcc184d82669513975561f2d2ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.037ex; height:2.509ex;" alt="{\displaystyle k_{t}}" loading="lazy"> is characterized by the <a href="Binomial_distribution" title="Binomial distribution">Binomial distribution</a>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(k_{t}=k)={K \choose k}p_{t}^{k}(1-p_{t})^{K-k},\,\quad \quad k=0,1,\dots ,K.}</annotation>

</semantics>

</math><img src="./f1a4c1f3d7475a2657e72a676e8cbd9256765617.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:54.007ex; height:6.176ex;" alt="{\displaystyle P(k_{t}=k)={K \choose k}p_{t}^{k}(1-p_{t})^{K-k},\,\quad \quad k=0,1,\dots ,K.}" loading="lazy"></dd></dl>

One can show that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} [k_{t}/K]=p_{t}}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} [k_{t}/K]=p_{t}}</annotation>

</semantics>

</math><img src="./cd5181c7a384eb72ef92e7e8d3c2a28987317f37.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.203ex; height:2.843ex;" alt="{\displaystyle \mathbb {E} [k_{t}/K]=p_{t}}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {var} [k_{t}/K]=p_{t}(1-p_{t})/K}">

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {var} [k_{t}/K]=p_{t}(1-p_{t})/K}</annotation>

</semantics>

</math><img src="./bae6417d69f13d531f232e16502f8d174c20441f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.991ex; height:2.843ex;" alt="{\displaystyle \operatorname {var} [k_{t}/K]=p_{t}(1-p_{t})/K}" loading="lazy">, so in the limit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K\to \infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K\to \infty }</annotation>

</semantics>

</math><img src="./d6e38ef3c3cb87a6ee1c85236a717d9fcdace4be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.004ex; height:2.176ex;" alt="{\displaystyle K\to \infty }" loading="lazy"> we are able to obtain <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{t}}</annotation>

</semantics>

</math><img src="./269b78ef9fb6e6bf8b70831dd8fcbe830c27ddd9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.085ex; height:2.009ex;" alt="{\displaystyle p_{t}}" loading="lazy">. Note that the variance is low if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{t}\approx 1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{t}\approx 1}</annotation>

</semantics>

</math><img src="./6a44ddbf1bcd78b3dc272b8531ca6b59819969e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:6.346ex; height:2.509ex;" alt="{\displaystyle p_{t}\approx 1}" loading="lazy">. Importance sampling is concerned with the determination and use of an alternate density function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{*}\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{*}\,}</annotation>

</semantics>

</math><img src="./d6bf0e81e78cf5ac9e395191e1178dee6ca0336c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle f_{*}\,}" loading="lazy">(for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy">), usually referred to as a biasing density, for the simulation experiment. This density allows the event <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {X\geq t\ }}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {X\geq t\ }}</annotation>

</semantics>

</math><img src="./2600b44f7aec0098c1c38bbb335224299cb357e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.499ex; height:2.343ex;" alt="{\displaystyle {X\geq t\ }}" loading="lazy"> to occur more frequently, so the sequence lengths <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"> gets smaller for a given <a href="Estimator" title="Estimator">estimator</a> variance. Alternatively, for a given <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy">, use of the biasing density results in a variance smaller than that of the conventional Monte Carlo estimate. From the definition of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{t}\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{t}\,}</annotation>

</semantics>

</math><img src="./0cb80d4b388c2ad1595cef75858a576030bac8a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.472ex; height:2.009ex;" alt="{\displaystyle p_{t}\,}" loading="lazy">, we can introduce <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{*}\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{*}\,}</annotation>

</semantics>

</math><img src="./d6bf0e81e78cf5ac9e395191e1178dee6ca0336c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle f_{*}\,}" loading="lazy"> as below.

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}p_{t}&=\mathbb {E} [1_{\{X\geq t\}}]\\[6pt]&=\int 1_{\{x\geq t\}}{\frac {f(x)}{f_{*}(x)}}f_{*}(x)\,dx\\[6pt]&=\mathbb {E} _{*}[1_{\{X\geq t\}}W(X)]\end{aligned}}}</annotation>

</semantics>

</math><img src="./112e60d66dbf1be735231238a29fdd2d327a7019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -7.338ex; width:28.711ex; height:15.843ex;" alt="{\displaystyle {\begin{aligned}p_{t}&=\mathbb {E} [1_{\{X\geq t\}}]\\[6pt]&=\int 1_{\{x\geq t\}}{\frac {f(x)}{f_{*}(x)}}f_{*}(x)\,dx\\[6pt]&=\mathbb {E} _{*}[1_{\{X\geq t\}}W(X)]\end{aligned}}}" loading="lazy"></dd></dl>

where

<mfrac>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W(\cdot )\equiv {\frac {f(\cdot )}{f_{*}(\cdot )}}}</annotation>

</semantics>

</math><img src="./98ed695b336d24052a88bf1143d19961ab63774f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:13.476ex; height:6.509ex;" alt="{\displaystyle W(\cdot )\equiv {\frac {f(\cdot )}{f_{*}(\cdot )}}}" loading="lazy"></dd></dl>

is a likelihood ratio and is referred to as the weighting function. The last equality in the above equation motivates the estimator

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {p}}_{t}={\frac {1}{K}}\,\sum _{i=1}^{K}1_{\{X_{i}\geq t\}}W(X_{i}),\,\quad \quad X_{i}\sim f_{*}}</annotation>

</semantics>

</math><img src="./c7be77b5aff416fdd8050ff601c1869fa27256b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; margin-left: -0.089ex; width:40.739ex; height:7.343ex;" alt="{\displaystyle {\hat {p}}_{t}={\frac {1}{K}}\,\sum _{i=1}^{K}1_{\{X_{i}\geq t\}}W(X_{i}),\,\quad \quad X_{i}\sim f_{*}}" loading="lazy"></dd></dl>

This is the importance sampling estimator of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{t}\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{t}\,}</annotation>

</semantics>

</math><img src="./0cb80d4b388c2ad1595cef75858a576030bac8a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.472ex; height:2.009ex;" alt="{\displaystyle p_{t}\,}" loading="lazy"> and is unbiased. That is, the estimation procedure is to generate i.i.d. samples from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{*}\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{*}\,}</annotation>

</semantics>

</math><img src="./d6bf0e81e78cf5ac9e395191e1178dee6ca0336c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle f_{*}\,}" loading="lazy"> and for each sample which exceeds <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t\,}</annotation>

</semantics>

</math><img src="./946383a7c6d1876177c662a95b369ced2ad99cd9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.227ex; height:2.009ex;" alt="{\displaystyle t\,}" loading="lazy">, the estimate is incremented by the weight <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W\,}</annotation>

</semantics>

</math><img src="./3d4ccedd54e0882bfffb73e8084f476e91e01aad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.822ex; height:2.176ex;" alt="{\displaystyle W\,}" loading="lazy"> evaluated at the sample value. The results are averaged over <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K\,}</annotation>

</semantics>

</math><img src="./492094dd0f8aec54c51b011cf9a1ae0aeaf89e38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.453ex; height:2.176ex;" alt="{\displaystyle K\,}" loading="lazy"> trials. The variance of the importance sampling estimator is easily shown to be

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

</mrow>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\operatorname {var} _{*}{\widehat {p}}_{t}&={\frac {1}{K}}\operatorname {var} _{*}[1_{\{X_{i}\geq t\}}W(X)]\\[5pt]&={\frac {1}{K}}\left\{\mathbb {E} _{*}[1_{\{X_{i}\geq t\}}^{2}W^{2}(X)]-p_{t}^{2}\right\}\\[5pt]&={\frac {1}{K}}\left\{\mathbb {E} [1_{\{X_{i}\geq t\}}W(X)]-p_{t}^{2}\right\}\end{aligned}}}</annotation>

</semantics>

</math><img src="./28fc7077a26acd68758c8677c795a98377b6b3ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -8.412ex; margin-bottom: -0.259ex; width:40.378ex; height:18.509ex;" alt="{\displaystyle {\begin{aligned}\operatorname {var} _{*}{\widehat {p}}_{t}&={\frac {1}{K}}\operatorname {var} _{*}[1_{\{X_{i}\geq t\}}W(X)]\\[5pt]&={\frac {1}{K}}\left\{\mathbb {E} _{*}[1_{\{X_{i}\geq t\}}^{2}W^{2}(X)]-p_{t}^{2}\right\}\\[5pt]&={\frac {1}{K}}\left\{\mathbb {E} [1_{\{X_{i}\geq t\}}W(X)]-p_{t}^{2}\right\}\end{aligned}}}" loading="lazy"></dd></dl>

Now, the importance sampling problem then focuses on finding a biasing density <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{*}\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{*}\,}</annotation>

</semantics>

</math><img src="./d6bf0e81e78cf5ac9e395191e1178dee6ca0336c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.581ex; height:2.509ex;" alt="{\displaystyle f_{*}\,}" loading="lazy"> such that the variance of the importance sampling estimator is less than the variance of the general Monte Carlo estimate. For some biasing density function, which minimizes the variance, and under certain conditions reduces it to zero, it is called an optimal biasing density function.

<div class="mw-heading mw-heading3"><h3 id="Conventional_biasing_methods">Conventional biasing methods</h3></div>

Although there are many kinds of biasing methods, the following two methods are most widely used in the applications of importance sampling.

<div class="mw-heading mw-heading4"><h4 id="Scaling">Scaling</h4></div>

Shifting probability mass into the event region <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {X\geq t\ }}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {X\geq t\ }}</annotation>

</semantics>

</math><img src="./2600b44f7aec0098c1c38bbb335224299cb357e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.499ex; height:2.343ex;" alt="{\displaystyle {X\geq t\ }}" loading="lazy"> by positive scaling of the random variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\,}</annotation>

</semantics>

</math><img src="./7028e89b7722d12ec0ea8780f26a9912456b63f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.367ex; height:2.176ex;" alt="{\displaystyle X\,}" loading="lazy"> with a number greater than unity has the effect of increasing the variance (mean also) of the density function. This results in a heavier tail of the density, leading to an increase in the event probability. Scaling is probably one of the earliest biasing methods known and has been extensively used in practice. It is simple to implement and usually provides conservative simulation gains as compared to other methods.

In importance sampling by scaling, the simulation density is chosen as the density function of the scaled random variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle aX\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle aX\,}</annotation>

</semantics>

</math><img src="./5d4b5e0bf482a464113670aa4663106b94087b6c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.597ex; height:2.176ex;" alt="{\displaystyle aX\,}" loading="lazy">, where usually <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a>1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a>1}</annotation>

</semantics>

</math><img src="./bc5b9d9fb0ff9d4455e75ccd29676bd7f33da80e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.491ex; height:2.176ex;" alt="{\displaystyle a>1}" loading="lazy"> for tail probability estimation. By transformation,

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{*}(x)={\frac {1}{a}}f{\bigg (}{\frac {x}{a}}{\bigg )}\,}</annotation>

</semantics>

</math><img src="./45f9dc327cb8374b7d1d5ef61f1185358938acdc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:17.75ex; height:6.176ex;" alt="{\displaystyle f_{*}(x)={\frac {1}{a}}f{\bigg (}{\frac {x}{a}}{\bigg )}\,}" loading="lazy"></dd></dl>

and the weighting function is

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W(x)=a{\frac {f(x)}{f(x/a)}}\,}</annotation>

</semantics>

</math><img src="./84263094de705adaf8fa001f754ac441130b2600.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:17.936ex; height:6.509ex;" alt="{\displaystyle W(x)=a{\frac {f(x)}{f(x/a)}}\,}" loading="lazy"></dd></dl>

While scaling shifts probability mass into the desired event region, it also pushes mass into the complementary region <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X<t\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X<t\,}</annotation>

</semantics>

</math><img src="./af88312f498422a9caecd3a38234b918a135ab67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.305ex; height:2.176ex;" alt="{\displaystyle X<t\,}" loading="lazy"> which is undesirable. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\,}</annotation>

</semantics>

</math><img src="./7028e89b7722d12ec0ea8780f26a9912456b63f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.367ex; height:2.176ex;" alt="{\displaystyle X\,}" loading="lazy"> is a sum of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\,}</annotation>

</semantics>

</math><img src="./205e33e6845813cc72ca346b896a7945f90ca373.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.782ex; height:1.676ex;" alt="{\displaystyle n\,}" loading="lazy"> random variables, the spreading of mass takes place in an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\,}</annotation>

</semantics>

</math><img src="./205e33e6845813cc72ca346b896a7945f90ca373.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.782ex; height:1.676ex;" alt="{\displaystyle n\,}" loading="lazy"> dimensional space. The consequence of this is a decreasing importance sampling gain for increasing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\,}</annotation>

</semantics>

</math><img src="./205e33e6845813cc72ca346b896a7945f90ca373.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.782ex; height:1.676ex;" alt="{\displaystyle n\,}" loading="lazy">, and is called the dimensionality effect.

A modern version of importance sampling by scaling is e.g. so-called sigma-scaled sampling (SSS) which is running multiple Monte Carlo (MC) analysis with different scaling factors. In opposite to many other high yield estimation methods (like worst-case distances WCD) SSS does not suffer much from the dimensionality problem. Also addressing multiple MC outputs causes no degradation in efficiency. On the other hand, as WCD, SSS is only designed for Gaussian statistical variables, and in opposite to WCD, the SSS method is not designed to provide accurate statistical corners. Another SSS disadvantage is that the MC runs with large scale factors may become difficult, e. g. due to model and simulator convergence problems. In addition, in SSS we face a strong bias-variance trade-off: Using large scale factors, we obtain quite stable yield results, but the larger the scale factors, the larger the bias error. If the advantages of SSS does not matter much in the application of interest, then often other methods are more efficient.

<div class="mw-heading mw-heading4"><h4 id="Translation">Translation</h4></div>

Another simple and effective biasing technique employs translation of the density function (and hence random variable) to place much of its probability mass in the rare event region. Translation does not suffer from a dimensionality effect and has been successfully used in several applications relating to simulation of <a href="Digital_communication" class="mw-redirect" title="Digital communication">digital communication</a> systems. It often provides better simulation gains than scaling. In biasing by translation, the simulation density is given by

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{*}(x)=f(x-c),\quad c>0\,}</annotation>

</semantics>

</math><img src="./68947b5d717c5838e845c048426ed12dacda7700.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.707ex; height:2.843ex;" alt="{\displaystyle f_{*}(x)=f(x-c),\quad c>0\,}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\,}</annotation>

</semantics>

</math><img src="./8573e7d95140b0d4068258d8162e189563baee6b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.394ex; height:1.676ex;" alt="{\displaystyle c\,}" loading="lazy"> is the amount of shift and is to be chosen to minimize the variance of the importance sampling estimator.

<div class="mw-heading mw-heading3"><h3 id="Effects_of_system_complexity">Effects of system complexity</h3></div>

The fundamental problem with importance sampling is that designing good biased distributions becomes more complicated as the system complexity increases. Complex systems are the systems with long memory since complex processing of a few inputs is much easier to handle. This dimensionality or memory can cause problems in three ways:

<ul><li>long memory (severe <a href="Intersymbol_interference" title="Intersymbol interference">intersymbol interference</a> (ISI))</li>

<li>unknown memory (<a href="Viterbi_decoder" title="Viterbi decoder">Viterbi decoders</a>)</li>

<li>possibly infinite memory (adaptive equalizers)</li></ul>

In principle, the importance sampling ideas remain the same in these situations, but the design becomes much harder. A successful approach to combat this problem is essentially breaking down a simulation into several smaller, more sharply defined subproblems. Then importance sampling strategies are used to target each of the simpler subproblems. Examples of techniques to break the simulation down are conditioning and error-event simulation (EES) and regenerative simulation.

<div class="mw-heading mw-heading3"><h3 id="Evaluation_of_importance_sampling">Evaluation of importance sampling</h3></div>

In order to identify successful importance sampling techniques, it is useful to be able to quantify the run-time savings due to the use of the importance sampling approach. The performance measure commonly used is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}">

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}</annotation>

</semantics>

</math><img src="./118c660f9891d296c274ffb77f2c96f246d1ad12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.533ex; height:3.176ex;" alt="{\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}" loading="lazy">, and this can be interpreted as the speed-up factor by which the importance sampling estimator achieves the same precision as the MC estimator. This has to be computed empirically since the estimator variances are not likely to be analytically possible when their mean is intractable. Other useful concepts in quantifying an importance sampling estimator are the variance bounds and the notion of asymptotic efficiency. One related measure is the so-called Effective Sample Size (ESS).<a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading3"><h3 id="Variance_cost_function">Variance cost function</h3></div>

Variance is not the only possible <a href="Loss_function" title="Loss function">cost function</a> for a simulation, and other cost functions, such as the mean absolute deviation, are used in various statistical applications. Nevertheless, the variance is the primary cost function addressed in the literature, probably due to the use of variances in <a href="Confidence_interval" title="Confidence interval">confidence intervals</a> and in the performance measure <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}">

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}</annotation>

</semantics>

</math><img src="./118c660f9891d296c274ffb77f2c96f246d1ad12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.533ex; height:3.176ex;" alt="{\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}" loading="lazy">.

An associated issue is the fact that the ratio <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}">

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}</annotation>

</semantics>

</math><img src="./118c660f9891d296c274ffb77f2c96f246d1ad12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.533ex; height:3.176ex;" alt="{\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}" loading="lazy"> overestimates the run-time savings due to importance sampling since it does not include the extra computing time required to compute the weight function. Hence, some people evaluate the net run-time improvement by various means. Perhaps a more serious overhead to importance sampling is the time taken to devise and program the technique and analytically derive the desired weight function.

<div class="mw-heading mw-heading3"><h3 id="Multiple_and_adaptive_importance_sampling">Multiple and adaptive importance sampling</h3></div>

When different proposal distributions, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i}(x)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i}(x)}</annotation>

</semantics>

</math><img src="./5e0c405bd84a5e6361d1d36aa625891bb16b02e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.048ex; height:2.843ex;" alt="{\displaystyle g_{i}(x)}" loading="lazy"> , <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=1,\ldots ,n,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=1,\ldots ,n,}</annotation>

</semantics>

</math><img src="./959435349dbcf868b5468d0ae851972fc8833d75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.283ex; height:2.509ex;" alt="{\displaystyle i=1,\ldots ,n,}" loading="lazy"> are jointly used for drawing the samples <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1},\ldots ,x_{n},}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1},\ldots ,x_{n},}</annotation>

</semantics>

</math><img src="./8fb4ea72660b223c376e371c2301215a39e53a55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.757ex; height:2.009ex;" alt="{\displaystyle x_{1},\ldots ,x_{n},}" loading="lazy"> different proper weighting functions can be employed (e.g., see <a href="#cite_note-7">[7]</a><a href="#cite_note-8">[8]</a><a href="#cite_note-9">[9]</a><a href="#cite_note-10">[10]</a>). In an adaptive setting, the proposal distributions, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i,t}(x)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i,t}(x)}</annotation>

</semantics>

</math><img src="./7b6b1ad075ce79cba990cceb2e41433ff727952f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.099ex; height:3.009ex;" alt="{\displaystyle g_{i,t}(x)}" loading="lazy"> , <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=1,\ldots ,n,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=1,\ldots ,n,}</annotation>

</semantics>

</math><img src="./959435349dbcf868b5468d0ae851972fc8833d75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.283ex; height:2.509ex;" alt="{\displaystyle i=1,\ldots ,n,}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=1,\ldots ,T,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=1,\ldots ,T,}</annotation>

</semantics>

</math><img src="./58caf6d98ce9653a27c9da3cc8f6228f9b0b21b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.562ex; height:2.509ex;" alt="{\displaystyle t=1,\ldots ,T,}" loading="lazy"> are updated each iteration <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> of the adaptive importance sampling algorithm. Hence, since a population of proposal densities is used, several suitable combinations of sampling and weighting schemes can be employed.<a href="#cite_note-11">[11]</a><a href="#cite_note-12">[12]</a><a href="#cite_note-13">[13]</a><a href="#cite_note-14">[14]</a><a href="#cite_note-15">[15]</a><a href="#cite_note-16">[16]</a><a href="#cite_note-17">[17]</a>

<ul><li><a href="Monte_Carlo_method" title="Monte Carlo method">Monte Carlo method</a></li>

<li><a href="Variance_reduction" title="Variance reduction">Variance reduction</a></li>

<li><a href="Stratified_sampling" title="Stratified sampling">Stratified sampling</a></li>

<li><a href="Monte_Carlo_integration#Recursive_stratified_sampling" title="Monte Carlo integration">Recursive stratified sampling</a></li>

<li><a href="VEGAS_algorithm" title="VEGAS algorithm">VEGAS algorithm</a></li>

<li><a href="Particle_filter" title="Particle filter">Particle filter</a> — a sequential Monte Carlo method, which uses importance sampling</li>

<li><a href="Auxiliary_field_Monte_Carlo" class="mw-redirect" title="Auxiliary field Monte Carlo">Auxiliary field Monte Carlo</a></li>

<li><a href="Rejection_sampling" title="Rejection sampling">Rejection sampling</a></li>

<li><a href="Variable_bitrate" title="Variable bitrate">Variable bitrate</a> — a common audio application of importance sampling</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFKloekvan_Dijk1978" class="citation journal cs1">Kloek, T.; van Dijk, H. K. (1978). <a rel="nofollow" class="external text" href="https://ageconsearch.umn.edu/record/272139/files/erasmus076.pdf">"Bayesian Estimates of Equation System Parameters: An Application of Integration by Monte Carlo"</a> (PDF). <a href="Econometrica" title="Econometrica">Econometrica</a>. 46 (1): 1–19. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F1913641">10.2307/1913641</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/1913641">1913641</a>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFGoertzle1949" class="citation journal cs1"><a href="Gerald_Goertzel" title="Gerald Goertzel">Goertzle, G.</a> (1949). "Quota Sampling and Importance Functions in Stochastic Solution of Particle Problems". Technical Report ORNL-434, Oak Ridge National Laboratory. Aecd; 2793. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/2027%2Fmdp.39015086443671">2027/mdp.39015086443671</a>.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFKahnHarris1949" class="citation journal cs1"><a href="Herman_Kahn" title="Herman Kahn">Kahn, H.</a>; <a href="Theodore_E._Harris" class="mw-redirect" title="Theodore E. Harris">Harris, T. E.</a> (1949). "Estimation of Particle Transmission by Random Sampling". Monte Carlo Method. Applied Mathematics Series. 12. National Bureau of Standards.: 27–30.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFBurdaGrosseSalakhutdinov2016" class="citation journal cs1">Burda, Yuri; Grosse, Roger; Salakhutdinov, Ruslan (2016). "Importance Weighted Autoencoders". Proceedings of the 4th International Conference on Learning Representations (ICLR). <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1509.00519">1509.00519</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> Rubinstein, R. Y., & <a href="Dirk_Kroese" title="Dirk Kroese">Kroese, D. P.</a> (2011). Simulation and the Monte Carlo method (Vol. 707). John Wiley & Sons.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFMartinoElviraLouzada2017" class="citation journal cs1">Martino, Luca; Elvira, Víctor; Louzada, Francisco (2017). "Effective sample size for importance sampling based on discrepancy measures". Signal Processing. 131: 386–401. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1602.03572">1602.03572</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.sigpro.2016.08.025">10.1016/j.sigpro.2016.08.025</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:26317735">26317735</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFVeachGuibas1995" class="citation book cs1">Veach, Eric; Guibas, Leonidas J. (1995-01-01). <a rel="nofollow" class="external text" href="https://archive.org/details/computergraphics00sigg/page/419">"Optimally combining sampling techniques for Monte Carlo rendering"</a>. Proceedings of the 22nd annual conference on Computer graphics and interactive techniques - SIGGRAPH '95. New York, NY, USA: ACM. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/computergraphics00sigg/page/419">419–428</a>. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.127.8105">10.1.1.127.8105</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F218380.218498">10.1145/218380.218498</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89791-701-8</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207194026">207194026</a>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFOwenAssociate2000" class="citation journal cs1">Owen, Art; Associate, Yi Zhou (2000-03-01). "Safe and Effective Importance Sampling". Journal of the American Statistical Association. 95 (449): 135–143. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.4536">10.1.1.36.4536</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F01621459.2000.10473909">10.1080/01621459.2000.10473909</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0162-1459">0162-1459</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:119761472">119761472</a>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFElviraMartinoLuengoBugallo2015" class="citation journal cs1">Elvira, V.; Martino, L.; Luengo, D.; Bugallo, M.F. (2015-10-01). "Efficient Multiple Importance Sampling Estimators". IEEE Signal Processing Letters. 22 (10): 1757–1761. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1505.05391">1505.05391</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2015ISPL...22.1757E">2015ISPL...22.1757E</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FLSP.2015.2432078">10.1109/LSP.2015.2432078</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1070-9908">1070-9908</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14504598">14504598</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFElviraMartinoLuengoBugallo2017" class="citation journal cs1">Elvira, Víctor; Martino, Luca; Luengo, David; Bugallo, Mónica F. (2017). "Improving population Monte Carlo: Alternative weighting and resampling schemes". Signal Processing. 131: 77–91. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1607.02758">1607.02758</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.sigpro.2016.07.012">10.1016/j.sigpro.2016.07.012</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:205171823">205171823</a>.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFCappéGuillinMarinRobert2004" class="citation journal cs1">Cappé, O.; Guillin, A.; Marin, J. M.; Robert, C. P. (2004-12-01). "Population Monte Carlo". Journal of Computational and Graphical Statistics. 13 (4): 907–929. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1198%2F106186004X12803">10.1198/106186004X12803</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1061-8600">1061-8600</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:119690181">119690181</a>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFMartinoElviraLuengoCorander2017" class="citation journal cs1">Martino, L.; Elvira, V.; Luengo, D.; Corander, J. (2017-05-01). "Layered adaptive importance sampling". Statistics and Computing. 27 (3): 599–623. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1505.04732">1505.04732</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs11222-016-9642-5">10.1007/s11222-016-9642-5</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0960-3174">0960-3174</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2508031">2508031</a>.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFCappéDoucGuillinMarin2008" class="citation journal cs1">Cappé, Olivier; Douc, Randal; Guillin, Arnaud; Marin, Jean-Michel; Robert, Christian P. (2008-04-25). "Adaptive importance sampling in general mixture classes". Statistics and Computing. 18 (4): 447–459. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0710.4242">0710.4242</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs11222-008-9059-x">10.1007/s11222-008-9059-x</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0960-3174">0960-3174</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:483916">483916</a>.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFCornuetMarinMiraRobert2012" class="citation journal cs1">Cornuet, Jean-Marie; Marin, Jean-Michel; <a href="Antonietta_Mira" title="Antonietta Mira">Mira, Antonietta</a>; Robert, Christian P. (2012-12-01). "Adaptive Multiple Importance Sampling". Scandinavian Journal of Statistics. 39 (4): 798–812. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0907.1254">0907.1254</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1111%2Fj.1467-9469.2011.00756.x">10.1111/j.1467-9469.2011.00756.x</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1467-9469">1467-9469</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17191248">17191248</a>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFMartinoElviraLuengoCorander2015" class="citation journal cs1">Martino, L.; Elvira, V.; Luengo, D.; Corander, J. (2015-08-01). "An Adaptive Population Importance Sampler: Learning From Uncertainty". IEEE Transactions on Signal Processing. 63 (16): 4422–4437. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2015ITSP...63.4422M">2015ITSP...63.4422M</a>. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.464.9395">10.1.1.464.9395</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTSP.2015.2440215">10.1109/TSP.2015.2440215</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1053-587X">1053-587X</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17017431">17017431</a>.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite id="CITEREFBugalloMartinoCorander2015" class="citation journal cs1">Bugallo, Mónica F.; Martino, Luca; Corander, Jukka (2015-12-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.dsp.2015.05.014">"Adaptive importance sampling in signal processing"</a>. Digital Signal Processing. Special Issue in Honour of William J. (Bill) Fitzgerald. 47: 36–49. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.dsp.2015.05.014">10.1016/j.dsp.2015.05.014</a>.</cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite id="CITEREFBugalloElviraMartinoLuengo2017" class="citation journal cs1">Bugallo, M. F.; Elvira, V.; Martino, L.; Luengo, D.; Miguez, J.; Djuric, P. M. (July 2017). "Adaptive Importance Sampling: The past, the present, and the future". IEEE Signal Processing Magazine. 34 (4): 60–79. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2017ISPM...34...60B">2017ISPM...34...60B</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Fmsp.2017.2699226">10.1109/msp.2017.2699226</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1053-5888">1053-5888</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5619054">5619054</a>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFArouna2004" class="citation journal cs1">Arouna, Bouhari (2004). "Adaptative Monte Carlo Method, A Variance Reduction Technique". Monte Carlo Methods and Their Applications. 10 (1): 1–24. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1515%2F156939604323091180">10.1515/156939604323091180</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:21949573">21949573</a>.</cite></li>

<li><cite id="CITEREFBucklew2004" class="citation book cs1">Bucklew, James Antonio (2004). Introduction to Rare Event Simulation. New York: Springer-Verlag.</cite></li>

<li><cite id="CITEREFDoucetde_FreitasGordon2001" class="citation book cs1">Doucet, A.; de Freitas, N.; Gordon, N. (2001). Sequential Monte Carlo Methods in Practice. Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-95146-1</bdi>.</cite></li>

<li><cite id="CITEREFFerrariBellini2001" class="citation book cs1">Ferrari, M.; Bellini, S. (2001). "Importance sampling simulation of turbo product codes". ICC 2001. IEEE International Conference on Communications. Conference Record (Cat. No.01CH37240). Vol. 9. pp. 2773–2777. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FICC.2001.936655">10.1109/ICC.2001.936655</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7803-7097-5</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5158473">5158473</a>.</cite></li>

<li><cite id="CITEREFMazonka2016" class="citation journal cs1">Mazonka, Oleg (2016). <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/303859967_Easy_As_Pi_The_Importance_Sampling_Method">"Easy as Pi: The Importance Sampling Method"</a>. Journal of Reference. 16.</cite></li>

<li><cite id="CITEREFOberg2001" class="citation book cs1">Oberg, Tommy (2001). Modulation, Detection, and Coding. New York: John Wiley & Sons.</cite></li>

<li><cite id="CITEREFPressTeukolskyVetterlingFlannery2007" class="citation book cs1">Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=411">"Section 7.9.1 Importance Sampling"</a>. Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-88068-8</bdi>. Archived from <a rel="nofollow" class="external text" href="http://apps.nrbook.com/empanel/index.html#pg=411">the original</a> on 2011-08-11. Retrieved 2011-08-12.</cite></li>

<li><cite id="CITEREFRipley1987" class="citation book cs1">Ripley, B. D. (1987). Stochastic Simulation. Wiley & Sons.</cite></li>

<li><cite id="CITEREFSmithShafiGao1997" class="citation journal cs1">Smith, P. J.; Shafi, M.; Gao, H. (1997). "Quick simulation: A review of importance sampling techniques in communication systems". IEEE Journal on Selected Areas in Communications. 15 (4): 597–613. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F49.585771">10.1109/49.585771</a>.</cite></li>

<li><cite id="CITEREFSrinivasan2002" class="citation book cs1">Srinivasan, R. (2002). Importance sampling – Applications in communications and detection. Berlin: Springer-Verlag.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www-sigproc.eng.cam.ac.uk/smc/">Sequential Monte Carlo Methods (Particle Filtering)</a> homepage on University of Cambridge</li>

<li><a rel="nofollow" class="external text" href="http://www.iop.org/EJ/abstract/0143-0807/22/4/315">Introduction to importance sampling in rare-event simulations</a> European journal of Physics. PDF document.</li>

<li><a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=1030470">Adaptive Monte Carlo methods for rare event simulations</a> Winter Simulation Conference</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-09" href="https://en.wikipedia.org/wiki/?title=Importance_sampling&oldid=1289627548">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>